/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.ssa;

import java.util.ArrayList;
import java.util.BitSet;

import com.android.dx.rop.code.RegisterSpec;
import com.android.dx.rop.code.RopMethod;
import com.android.dx.util.IntIterator;

/**
 * Converts ROP methods to SSA Methods
 */
public class SsaConverter {

	public static final boolean DEBUG = false;

	/**
	 * Returns an SSA representation, edge-split and with phi functions placed.
	 * 
	 * @param rmeth
	 *            input
	 * @param paramWidth
	 *            the total width, in register-units, of the method's parameters
	 * @param isStatic
	 *            {@code true} if this method has no {@code this} pointer
	 *            argument
	 * @return output in SSA form
	 */
	public static SsaMethod convertToSsaMethod(RopMethod rmeth, int paramWidth,
			boolean isStatic) {
		SsaMethod result = SsaMethod.newFromRopMethod(rmeth, paramWidth,
				isStatic);

		edgeSplit(result);

		LocalVariableInfo localInfo = LocalVariableExtractor.extract(result);

		placePhiFunctions(result, localInfo, 0);
		new SsaRenamer(result).run();

		/*
		 * The exit block, added here, is not considered for edge splitting or
		 * phi placement since no actual control flows to it.
		 */
		result.makeExitBlock();

		return result;
	}

	/**
	 * Updates an SSA representation, placing phi functions and renaming all
	 * registers above a certain threshold number.
	 * 
	 * @param ssaMeth
	 *            input
	 * @param threshold
	 *            registers below this number are unchanged
	 */
	public static void updateSsaMethod(SsaMethod ssaMeth, int threshold) {
		LocalVariableInfo localInfo = LocalVariableExtractor.extract(ssaMeth);
		placePhiFunctions(ssaMeth, localInfo, threshold);
		new SsaRenamer(ssaMeth, threshold).run();
	}

	/**
	 * Returns an SSA represention with only the edge-splitter run.
	 * 
	 * @param rmeth
	 *            method to process
	 * @param paramWidth
	 *            width of all arguments in the method
	 * @param isStatic
	 *            {@code true} if this method has no {@code this} pointer
	 *            argument
	 * @return an SSA represention with only the edge-splitter run
	 */
	public static SsaMethod testEdgeSplit(RopMethod rmeth, int paramWidth,
			boolean isStatic) {
		SsaMethod result;

		result = SsaMethod.newFromRopMethod(rmeth, paramWidth, isStatic);

		edgeSplit(result);
		return result;
	}

	/**
	 * Returns an SSA represention with only the steps through the phi placement
	 * run.
	 * 
	 * @param rmeth
	 *            method to process
	 * @param paramWidth
	 *            width of all arguments in the method
	 * @param isStatic
	 *            {@code true} if this method has no {@code this} pointer
	 *            argument
	 * @return an SSA represention with only the edge-splitter run
	 */
	public static SsaMethod testPhiPlacement(RopMethod rmeth, int paramWidth,
			boolean isStatic) {
		SsaMethod result;

		result = SsaMethod.newFromRopMethod(rmeth, paramWidth, isStatic);

		edgeSplit(result);

		LocalVariableInfo localInfo = LocalVariableExtractor.extract(result);

		placePhiFunctions(result, localInfo, 0);
		return result;
	}

	/**
	 * See Appel section 19.1: Converts CFG into "edge-split" form, such that
	 * each node either a unique successor or unique predecessor.
	 * <p>
	 * In addition, the SSA form we use enforces a further constraint, requiring
	 * each block with a final instruction that returns a value to have a
	 * primary successor that has no other predecessor. This ensures move
	 * statements can always be inserted correctly when phi statements are
	 * removed.
	 * 
	 * @param result
	 *            method to process
	 */
	private static void edgeSplit(SsaMethod result) {
		edgeSplitPredecessors(result);
		edgeSplitMoveExceptionsAndResults(result);
		edgeSplitSuccessors(result);
	}

	/**
	 * Inserts Z nodes as new predecessors for every node that has multiple
	 * successors and multiple predecessors.
	 * 
	 * @param result
	 *            {@code non-null;} method to process
	 */
	private static void edgeSplitPredecessors(SsaMethod result) {
		ArrayList<SsaBasicBlock> blocks = result.getBlocks();

		/*
		 * New blocks are added to the end of the block list during this
		 * iteration.
		 */
		for (int i = blocks.size() - 1; i >= 0; i--) {
			SsaBasicBlock block = blocks.get(i);
			if (nodeNeedsUniquePredecessor(block)) {
				block.insertNewPredecessor();
			}
		}
	}

	/**
	 * @param block
	 *            {@code non-null;} block in question
	 * @return {@code true} if this node needs to have a unique predecessor
	 *         created for it
	 */
	private static boolean nodeNeedsUniquePredecessor(SsaBasicBlock block) {
		/*
		 * Any block with that has both multiple successors and multiple
		 * predecessors needs a new predecessor node.
		 */

		int countPredecessors = block.getPredecessors().cardinality();
		int countSuccessors = block.getSuccessors().cardinality();

		return (countPredecessors > 1 && countSuccessors > 1);
	}

	/**
	 * In ROP form, move-exception must occur as the first insn in a block
	 * immediately succeeding the insn that could thrown an exception. We may
	 * need room to insert move insns later, so make sure to split any block
	 * that starts with a move-exception such that there is a unique
	 * move-exception block for each predecessor.
	 * 
	 * @param ssaMeth
	 *            method to process
	 */
	private static void edgeSplitMoveExceptionsAndResults(SsaMethod ssaMeth) {
		ArrayList<SsaBasicBlock> blocks = ssaMeth.getBlocks();

		/*
		 * New blocks are added to the end of the block list during this
		 * iteration.
		 */
		for (int i = blocks.size() - 1; i >= 0; i--) {
			SsaBasicBlock block = blocks.get(i);

			/*
			 * Any block that starts with a move-exception and has more than one
			 * predecessor...
			 */
			if (!block.isExitBlock()
					&& block.getPredecessors().cardinality() > 1
					&& block.getInsns().get(0).isMoveException()) {

				// block.getPredecessors() is changed in the loop below.
				BitSet preds = (BitSet) block.getPredecessors().clone();
				for (int j = preds.nextSetBit(0); j >= 0; j = preds
						.nextSetBit(j + 1)) {
					SsaBasicBlock predecessor = blocks.get(j);
					SsaBasicBlock zNode = predecessor.insertNewSuccessor(block);

					/*
					 * Make sure to place the move-exception as the first insn.
					 */
					zNode.getInsns().add(0, block.getInsns().get(0).clone());
				}

				// Remove the move-exception from the original block.
				block.getInsns().remove(0);
			}
		}
	}

	/**
	 * Inserts Z nodes for every node that needs a new successor.
	 * 
	 * @param result
	 *            {@code non-null;} method to process
	 */
	private static void edgeSplitSuccessors(SsaMethod result) {
		ArrayList<SsaBasicBlock> blocks = result.getBlocks();

		/*
		 * New blocks are added to the end of the block list during this
		 * iteration.
		 */
		for (int i = blocks.size() - 1; i >= 0; i--) {
			SsaBasicBlock block = blocks.get(i);

			// Successors list is modified in loop below.
			BitSet successors = (BitSet) block.getSuccessors().clone();
			for (int j = successors.nextSetBit(0); j >= 0; j = successors
					.nextSetBit(j + 1)) {

				SsaBasicBlock succ = blocks.get(j);

				if (needsNewSuccessor(block, succ)) {
					block.insertNewSuccessor(succ);
				}
			}
		}
	}

	/**
	 * Returns {@code true} if block and successor need a Z-node between them.
	 * Presently, this is {@code true} if the final instruction has any sources
	 * or results and the current successor block has more than one predecessor.
	 * 
	 * @param block
	 *            predecessor node
	 * @param succ
	 *            successor node
	 * @return {@code true} if a Z node is needed
	 */
	private static boolean needsNewSuccessor(SsaBasicBlock block,
			SsaBasicBlock succ) {
		ArrayList<SsaInsn> insns = block.getInsns();
		SsaInsn lastInsn = insns.get(insns.size() - 1);

		return ((lastInsn.getResult() != null) || (lastInsn.getSources().size() > 0))
				&& succ.getPredecessors().cardinality() > 1;
	}

	/**
	 * See Appel algorithm 19.6: Place Phi functions in appropriate locations.
	 * 
	 * @param ssaMeth
	 *            {@code non-null;} method to process. Modifications are made
	 *            in-place.
	 * @param localInfo
	 *            {@code non-null;} local variable info, used when placing phis
	 * @param threshold
	 *            registers below this number are ignored
	 */
	private static void placePhiFunctions(SsaMethod ssaMeth,
			LocalVariableInfo localInfo, int threshold) {
		ArrayList<SsaBasicBlock> ssaBlocks;
		int regCount;
		int blockCount;

		ssaBlocks = ssaMeth.getBlocks();
		blockCount = ssaBlocks.size();
		regCount = ssaMeth.getRegCount() - threshold;

		DomFront df = new DomFront(ssaMeth);
		DomFront.DomInfo[] domInfos = df.run();

		// Bit set of registers vs block index "definition sites"
		BitSet[] defsites = new BitSet[regCount];

		// Bit set of registers vs block index "phi placement sites"
		BitSet[] phisites = new BitSet[regCount];

		for (int i = 0; i < regCount; i++) {
			defsites[i] = new BitSet(blockCount);
			phisites[i] = new BitSet(blockCount);
		}

		/*
		 * For each register, build a set of all basic blocks where containing
		 * an assignment to that register.
		 */
		for (int bi = 0, s = ssaBlocks.size(); bi < s; bi++) {
			SsaBasicBlock b = ssaBlocks.get(bi);

			for (SsaInsn insn : b.getInsns()) {
				RegisterSpec rs = insn.getResult();

				if (rs != null && rs.getReg() - threshold >= 0) {
					defsites[rs.getReg() - threshold].set(bi);
				}
			}
		}

		if (DEBUG) {
			System.out.println("defsites");

			for (int i = 0; i < regCount; i++) {
				StringBuilder sb = new StringBuilder();
				sb.append('v').append(i).append(": ");
				sb.append(defsites[i].toString());
				System.out.println(sb);
			}
		}

		BitSet worklist;

		/*
		 * For each register, compute all locations for phi placement based on
		 * dominance-frontier algorithm.
		 */
		for (int reg = 0, s = regCount; reg < s; reg++) {
			int workBlockIndex;

			/* Worklist set starts out with each node where reg is assigned. */

			worklist = (BitSet) (defsites[reg].clone());

			while (0 <= (workBlockIndex = worklist.nextSetBit(0))) {
				worklist.clear(workBlockIndex);
				IntIterator dfIterator = domInfos[workBlockIndex].dominanceFrontiers
						.iterator();

				while (dfIterator.hasNext()) {
					int dfBlockIndex = dfIterator.next();

					if (!phisites[reg].get(dfBlockIndex)) {
						phisites[reg].set(dfBlockIndex);

						int tReg = reg + threshold;
						RegisterSpec rs = localInfo.getStarts(dfBlockIndex)
								.get(tReg);

						if (rs == null) {
							ssaBlocks.get(dfBlockIndex).addPhiInsnForReg(tReg);
						} else {
							ssaBlocks.get(dfBlockIndex).addPhiInsnForReg(rs);
						}

						if (!defsites[reg].get(dfBlockIndex)) {
							worklist.set(dfBlockIndex);
						}
					}
				}
			}
		}

		if (DEBUG) {
			System.out.println("phisites");

			for (int i = 0; i < regCount; i++) {
				StringBuilder sb = new StringBuilder();
				sb.append('v').append(i).append(": ");
				sb.append(phisites[i].toString());
				System.out.println(sb);
			}
		}
	}
}
